import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/20 9:05
 * @description 比赛时候想到了要贪心，将数组最大的数减少一半，然后重新寻找最大的数，继续减半，这样操作肯定
 * 最少，但是没有想到用堆来排序获取每次最大的值
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {5, 19, 8, 1};
        solution.halveArray(nums);
    }
    public int halveArray(int[] nums) {
        double sum = 0;
        // 维护一个大顶堆
        PriorityQueue<Double> pq = new PriorityQueue<>((o1, o2) -> Double.compare(o2, o1));
        for(int num: nums) {
            sum += num;
            pq.add((double) num);
        }
        double target = sum / 2;
        sum = 0;
        int cnt = 0;
        while (sum < target && !pq.isEmpty()) {
            Double max = pq.poll();
            sum += max / 2;
            pq.add(max / 2);
            cnt++;
        }
        return cnt;
    }

}
